<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"yuzhenxin.gitee.io","root":"/","scheme":"Muse","version":"7.8.0","exturl":false,"sidebar":{"position":"right","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="计算机基础数据结构树 k叉树n0个叶结点要构成哈夫曼树需要补充(n0-1)%(k-1)个叶结点，结果的带权路径长度WPL&#x3D;nk 树的先序遍历对应二叉树（根节点无右孩子）的先序遍历，树的后序遍历对应二叉树的中序遍历 森林的先序遍历对应二叉树的先序遍历，森林的后序遍历（也是中序遍历）对应二叉树的中序遍历 二叉树的先序遍历相当于入栈，中序遍历相当于出栈。（根左右的顺序，先序遍历就需要先访问根节点，入栈访">
<meta property="og:type" content="article">
<meta property="og:title" content="计算机基础">
<meta property="og:url" content="http://yuzhenxin.gitee.io/2020/12/23/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80/index.html">
<meta property="og:site_name" content="余振鑫的Hexo博客">
<meta property="og:description" content="计算机基础数据结构树 k叉树n0个叶结点要构成哈夫曼树需要补充(n0-1)%(k-1)个叶结点，结果的带权路径长度WPL&#x3D;nk 树的先序遍历对应二叉树（根节点无右孩子）的先序遍历，树的后序遍历对应二叉树的中序遍历 森林的先序遍历对应二叉树的先序遍历，森林的后序遍历（也是中序遍历）对应二叉树的中序遍历 二叉树的先序遍历相当于入栈，中序遍历相当于出栈。（根左右的顺序，先序遍历就需要先访问根节点，入栈访">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210317212320.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210317212403.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210311230819.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224133.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224158.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224206.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224216.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224226.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224234.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224242.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224249.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210320152831.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210320152842.png">
<meta property="og:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210320161251.png">
<meta property="article:published_time" content="2020-12-22T16:00:00.000Z">
<meta property="article:modified_time" content="2021-04-07T00:31:31.168Z">
<meta property="article:author" content="余振鑫">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/yuzhenxin/images/raw/master/img/20210317212320.png">

<link rel="canonical" href="http://yuzhenxin.gitee.io/2020/12/23/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>计算机基础 | 余振鑫的Hexo博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">余振鑫的Hexo博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">计算机笔记</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://yuzhenxin.gitee.io/2020/12/23/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="余振鑫">
      <meta itemprop="description" content="余振鑫的个人博客">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="余振鑫的Hexo博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          计算机基础
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2020-12-23 00:00:00" itemprop="dateCreated datePublished" datetime="2020-12-23T00:00:00+08:00">2020-12-23</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-04-07 08:31:31" itemprop="dateModified" datetime="2021-04-07T08:31:31+08:00">2021-04-07</time>
              </span>

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="计算机基础"><a href="#计算机基础" class="headerlink" title="计算机基础"></a>计算机基础</h1><h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><h3 id="树"><a href="#树" class="headerlink" title="树"></a>树</h3><ul>
<li>k叉树n0个叶结点要构成哈夫曼树需要补充(n0-1)%(k-1)个叶结点，结果的带权路径长度WPL=nk</li>
<li>树的先序遍历对应二叉树（根节点无右孩子）的先序遍历，树的后序遍历对应二叉树的中序遍历</li>
<li>森林的先序遍历对应二叉树的先序遍历，森林的后序遍历（也是中序遍历）对应二叉树的中序遍历</li>
<li>二叉树的先序遍历相当于入栈，中序遍历相当于出栈。（根左右的顺序，先序遍历就需要先访问根节点，入栈访问，中序遍历先访问左孩子，故出栈访问根节点）</li>
<li>二叉树转森林，断开右孩子，左孩子右兄弟</li>
<li>n0 = 1+n2+2n3+…</li>
<li>LL调整：新插入结点落在最小不平衡子树根节点的左孩子的左子树上</li>
<li>图的广度优先遍历相当于二叉树的层次遍历，深度优先遍历相当于二叉树的先序遍历</li>
<li>两个长度为m、n的升序链表合并为一个升/降序链表（尾插法和头插法），时间复杂度最好O(min(m,n))，最坏O(max(m,n))</li>
<li>B树根节点（非叶子结点）至少2个分支（一个关键字），非根非叶结点至少m/2取上界-1个关键字，至多k-1个关键字（k叉B树）</li>
</ul>
<h4 id="二叉排序树"><a href="#二叉排序树" class="headerlink" title="二叉排序树"></a>二叉排序树</h4><ol>
<li><strong>左</strong>子树上所有结点的值均<strong>小于或等于</strong>它的根结点的值。</li>
<li><strong>右</strong>子树上所有结点的值均<strong>大于或等于</strong>它的根结点的值。</li>
<li>左、右子树也分别为二叉排序树。</li>
</ol>
<h4 id="平衡二叉树"><a href="#平衡二叉树" class="headerlink" title="平衡二叉树"></a>平衡二叉树</h4><p>平衡二叉树又称AVL树，它是一种<strong>特殊的二叉排序树</strong>：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。使用了二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。</p>
<h5 id="调整"><a href="#调整" class="headerlink" title="调整"></a>调整</h5><ul>
<li><p>RR平衡旋转：左旋</p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210317212320.png" alt="image-20210317212313023"></p>
</li>
<li><p>LL平衡旋转：右旋</p>
</li>
<li><p>RL平衡旋转：先右旋再左旋</p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210317212403.png" alt="image-20210317212403292"></p>
</li>
<li><p>LR平衡旋转：先左旋再右旋</p>
</li>
</ul>
<h4 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h4><ul>
<li>节点是红色或黑色。</li>
<li>根节点是黑色。</li>
<li>每个叶子节点都是黑色的空节点（NIL节点）。</li>
<li>每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)</li>
<li>从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。</li>
<li><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210311230819.png" alt="image-20210311230819057"></li>
</ul>
<h3 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h3><ul>
<li><p>堆中某个节点的值总是不大于或不小于其父节点的值</p>
</li>
<li><p>堆总是一棵完全二叉树</p>
</li>
<li><p>堆排序删除该轮最大结点（大根堆的根节点）后，将底层最右边的结点移到根节点</p>
</li>
</ul>
<h3 id="散列表"><a href="#散列表" class="headerlink" title="散列表"></a>散列表</h3><ul>
<li>散列表查找成功ASL=几次找到元素/元素个数，查找失败ASL=几次找到空指针/可用表长（模数）</li>
</ul>
<h3 id="串"><a href="#串" class="headerlink" title="串"></a>串</h3><ul>
<li>KMP的nextval，当前值与next对应的值是否相同，相同就抄对方的nextval，不同就照抄next</li>
</ul>
<h3 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 快速排序</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">Partition</span><span class="params">(<span class="keyword">int</span> A[], <span class="keyword">int</span> low, <span class="keyword">int</span> high)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pivot = A[low]; <span class="comment">//将数组以A[low]划分左右</span></span><br><span class="line">    <span class="keyword">while</span> (low &lt; high) &#123;</span><br><span class="line">        <span class="comment">//在low的右侧找到第一个小于中轴的数</span></span><br><span class="line">        <span class="keyword">while</span> (low &lt; high &amp;&amp; A[high] &gt;= pivot) --high;</span><br><span class="line">        <span class="comment">//把这个数放到low处</span></span><br><span class="line">        A[low] = A[high];</span><br><span class="line">        <span class="comment">//在high的左侧找到第一个大于中轴的数</span></span><br><span class="line">        <span class="keyword">while</span> (low &lt; high &amp;&amp; A[low] &lt;= pivot) ++low;</span><br><span class="line">        <span class="comment">//把这个数放到high处</span></span><br><span class="line">        A[high] = A[low];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//low和high相遇时为划分左右的中轴</span></span><br><span class="line">    A[low] = pivot;</span><br><span class="line">    <span class="keyword">return</span> low;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//low和high为头尾元素下标</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">QuickSort</span><span class="params">(<span class="keyword">int</span> A[], <span class="keyword">int</span> low, <span class="keyword">int</span> high)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (low &lt; high) &#123;</span><br><span class="line">        <span class="keyword">int</span> pivot = Partition(A, low, high);</span><br><span class="line">        QuickSort(A, low, pivot - <span class="number">1</span>); <span class="comment">//递归完成左侧排序</span></span><br><span class="line">        QuickSort(A, pivot + <span class="number">1</span>, high); <span class="comment">//递归完成右侧排序</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="计算机组成原理"><a href="#计算机组成原理" class="headerlink" title="计算机组成原理"></a>计算机组成原理</h2><ul>
<li>补码（8位：-128~127）<ul>
<li>1000 0000作为补码的真值为-1或-128（-2^7）（负数的话不看符号位，大的真值就大）</li>
<li>1111 1111作为补码的真值为-1</li>
</ul>
</li>
<li>类型转换通过扩展机器数符号位</li>
<li>算术移位：符号位不动，负数补码左移添0右移添1，原码添0</li>
<li>溢出判断：符号位相同运算而结果符号不同</li>
<li>X的补码全反+1=-X的补码</li>
<li>补码一位乘法：最多n次移位，n+1次加法；原码运算符号位都单独出来，乘除结果符号位由异或得到；原码不恢复余数法（加减交替法）只在最终余数为负才恢复余数；补码除法，异号相除看够不够减，够减商0，不够商1</li>
<li>float的阶码1~254，偏移值-127</li>
<li>中断隐指令保存PC断点</li>
<li>Cache附加位：有效位、访问位、脏位；LRU的位数取决于log2(几路组相联)。</li>
</ul>
<h2 id="操作系统"><a href="#操作系统" class="headerlink" title="操作系统"></a>操作系统</h2><ul>
<li><p>用户发出open系统调用，提供文件名和访问路径参数；操作系统从外存调入FCB，返回用户文件描述符（指针），用户通过文件描述符找到FCB，调用read系统调用将数据读入内存。</p>
</li>
<li><p>管程相当于类，条件变量类似信号量，但是没有值，因此只能用于排队：阻塞（wait）或唤醒（signal），编译器实现对条件变量的互斥访问</p>
</li>
<li><p>只有FIFO可能会发生Belady异常</p>
</li>
<li><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224133.png" alt="image-20210130113735311" style="zoom:200%;" /></li>
<li><p>目录文件每一项包含文件名和索引结点指针，索引指针指向的索引结点包含文件属性和地址信息</p>
<p>文件分配基本单位是簇/块</p>
</li>
</ul>
<h2 id="计算机网络"><a href="#计算机网络" class="headerlink" title="计算机网络"></a>计算机网络</h2><p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224158.png" alt="image-20210130114348957"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224206.png" alt="image-20210130114200617"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224216.png" alt="image-20210130114205071"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224226.png" alt="image-20210130114255062"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224234.png" alt="image-20210130114309796"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224242.png" alt="image-20210130114313547"></p>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210307224249.png" alt="image-20210130114315859"></p>
<h3 id="TCP和UDP区别"><a href="#TCP和UDP区别" class="headerlink" title="TCP和UDP区别"></a>TCP和UDP区别</h3><p>TCP（TransmissionControl Protocol 传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层通信协议。</p>
<p>UDP是User Datagram Protocol，一种无连接的传输层协议，提供面向事务的简单不可靠信息传送服务。可靠性由上层应用实现，所以要实现udp可靠性传输，必须通过应用层来实现和控制。</p>
<h3 id="TCP三次握手和四次挥手过程及原因"><a href="#TCP三次握手和四次挥手过程及原因" class="headerlink" title="TCP三次握手和四次挥手过程及原因"></a>TCP三次握手和四次挥手过程及原因</h3><h4 id="三次握手过程"><a href="#三次握手过程" class="headerlink" title="三次握手过程"></a>三次握手过程</h4><p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210320152831.png" alt="image-20210320152824133"></p>
<ol>
<li>客户机向服务器发送连接请求，SYN和序列号seq（随机生成），进入SYN-SENT状态。</li>
<li>服务器接到请求后，发送确认ACK和同步信号SYN，还有序列号seq，进入SYN-RCVD状态</li>
<li>客户机再向服务器发送确认报文，ACK和seq，进入ESTABLISHED状态。此阶段可以携带报文，不携带则不消耗序列号</li>
</ol>
<h4 id="三次握手的原因"><a href="#三次握手的原因" class="headerlink" title="三次握手的原因"></a>三次握手的原因</h4><p>为了防止已失效的请求突然发送到服务器，产生错误。</p>
<ul>
<li>假设两次握手时客户机发送的第一个连接请求报文滞留到连接释放后才发送到服务器，B会以为又是一个新的连接请求，发送确认报文段，两次握手下就建立了连接，浪费资源。</li>
<li>假设客户机发送连接请求后就下线，服务器收到请求就会发送确认报文段，建立连接，浪费资源。</li>
</ul>
<h4 id="四次挥手过程"><a href="#四次挥手过程" class="headerlink" title="四次挥手过程"></a>四次挥手过程</h4><p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210320152842.png" alt="image-20210320152842153"></p>
<ol>
<li>客户机向服务器发送连接释放报文，FIN和seq，进入FIN-WAIT1状态。</li>
<li>服务器收到释放报文就发送确认报文，ACK和seq，进入CLOSE-WAIT状态。此时TCP连接处于半关闭状态，B仍可以发送给A数据</li>
<li>A收到B确认后，进入FIN-WAIT2状态，等待B发送连接释放报文</li>
<li>B发完数据后发送释放连接报文，FIN、ACK和seq，进入LAST-ACK状态</li>
<li>A收到连接释放报文就发送确认报文，ACK和seq，进入TIME-WAIT状态</li>
<li>B收到确认报文就进入CLOSED状态。</li>
<li>经过2MSL（最长报文段寿命）后，A进入CLOSED状态，结束。</li>
</ol>
<h4 id="设置TIME-WAIT原因"><a href="#设置TIME-WAIT原因" class="headerlink" title="设置TIME-WAIT原因"></a>设置TIME-WAIT原因</h4><ul>
<li>保证A发送的最后一个ACK能到达B，若丢失，B会超时重传FIN+ACK报文，A就能收到再重传。</li>
<li>A发完最后一个ACK后，经过2MSL就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。</li>
</ul>
<h4 id="四次挥手原因"><a href="#四次挥手原因" class="headerlink" title="四次挥手原因"></a>四次挥手原因</h4><ul>
<li>TCP全双工，关闭连接应由双方共同确认</li>
<li>假设三次挥手，B发送确认报文段就会立刻发送确认报文，会导致B向A还在发送数据时连接就被关闭。这样会导致A没有完整收到B所发的报文段</li>
</ul>
<h3 id="TCP拥塞控制"><a href="#TCP拥塞控制" class="headerlink" title="TCP拥塞控制"></a>TCP拥塞控制</h3><p>在发送数据时，将拥塞窗口的大小与接收端ack的窗口大小做比较，取较小者作为发送数据量的上限</p>
<ol>
<li>慢启动，每经过一个RTT，cwnd = cwnd*2; 呈指数上升</li>
<li>拥塞避免，cwnd达到阈值ssthresh。每当过了一个RTT，cwnd = cwnd + 1</li>
<li>阻塞发生：sshthresh = cwnd /2，cwnd重置为1</li>
<li>快重传，连续收到3个重复确认报文就重传，sshthresh = cwnd = cwnd /2</li>
<li>快恢复，cwnd = cwnd +1</li>
</ol>
<h3 id="从浏览器输入一个URL到返回响应的完整过程"><a href="#从浏览器输入一个URL到返回响应的完整过程" class="headerlink" title="从浏览器输入一个URL到返回响应的完整过程"></a>从浏览器输入一个URL到返回响应的完整过程</h3><ol>
<li>DNS解析<ol>
<li>递归查询本地域名服务器</li>
<li>本地域名服务器迭代访问根域名服务器、顶级域名服务器、权限域名服务器</li>
</ol>
</li>
<li>TCP连接</li>
<li>发送http请求</li>
<li>服务器响应http请求</li>
<li>浏览器解析html</li>
<li>断开TCP连接</li>
</ol>
<h3 id="Https和Http"><a href="#Https和Http" class="headerlink" title="Https和Http"></a>Https和Http</h3><p>HTTP基于TCP，HTTP使用TCP而不是UDP的原因在于（打开）一个网页必须传送很多数据，而TCP协议提供传输控制，按顺序组织数据，和错误纠正。</p>
<p>https协议需要到CA申请证书，一般免费证书很少，需要交费。<br>http是超文本传输协议，信息是明文传输；https 则是具有安全性的ssl加密传输协议。<br>http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。<br>http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。</p>
<ol>
<li>内容加密：采用混合加密技术，中间者无法直接查看明文内容</li>
<li>验证身份：通过证书认证客户端访问的是自己的服务器</li>
<li>保护数据完整性：防止传输的内容被中间人冒充或者篡改</li>
</ol>
<p><img src="https://gitee.com/yuzhenxin/images/raw/master/img/20210320161251.png" alt="image-20210320161251368"></p>
<ul>
<li>SSL在握手阶段依赖数字证书建立安全会话<ul>
<li>数字证书包含公钥和数字签名</li>
<li>明文 –&gt; hash运算 –&gt; 摘要 –&gt; 私钥加密 –&gt; 数字签名</li>
</ul>
</li>
<li>传输阶段使用对称加密算法加密（常见：DES、AES）</li>
</ul>
<h3 id="UDP保证可靠性传输"><a href="#UDP保证可靠性传输" class="headerlink" title="UDP保证可靠性传输"></a>UDP保证可靠性传输</h3><p>传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，实现转移到了应用层。</p>
<p>实现确认机制、重传机制、窗口确认机制。</p>
<h3 id="Get和Post"><a href="#Get和Post" class="headerlink" title="Get和Post"></a>Get和Post</h3><ul>
<li>get是获取数据，post是提交数据</li>
<li>GET在浏览器回退时是无害的，而POST会再次提交请求。</li>
<li>GET产生的URL地址可以被Bookmark，而POST不可以。</li>
<li>GET请求会被浏览器主动cache，而POST不会，除非手动设置。</li>
<li>GET请求只能进行url编码，而POST支持多种编码方式。</li>
<li>GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。</li>
<li>GET请求在URL中传送的参数是有长度限制的，而POST么有。</li>
<li>对参数的数据类型，GET只接受ASCII字符，而POST没有限制。</li>
<li>GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。</li>
<li>GET参数通过URL传递，POST放在Request body中。</li>
</ul>

    </div>

    
    
    

      <footer class="post-footer">

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2020/11/20/%E6%95%B0%E6%8D%AE%E5%BA%93/" rel="prev" title="数据库">
      <i class="fa fa-chevron-left"></i> 数据库
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/01/11/Java%E6%A1%86%E6%9E%B6/" rel="next" title="Java框架">
      Java框架 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80"><span class="nav-number">1.</span> <span class="nav-text">计算机基础</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">1.1.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%91"><span class="nav-number">1.1.1.</span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91"><span class="nav-number">1.1.1.1.</span> <span class="nav-text">二叉排序树</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.1.1.2.</span> <span class="nav-text">平衡二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#%E8%B0%83%E6%95%B4"><span class="nav-number">1.1.1.2.1.</span> <span class="nav-text">调整</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="nav-number">1.1.1.3.</span> <span class="nav-text">红黑树</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A0%86"><span class="nav-number">1.1.2.</span> <span class="nav-text">堆</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%A3%E5%88%97%E8%A1%A8"><span class="nav-number">1.1.3.</span> <span class="nav-text">散列表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%B2"><span class="nav-number">1.1.4.</span> <span class="nav-text">串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%8E%92%E5%BA%8F"><span class="nav-number">1.1.5.</span> <span class="nav-text">排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86"><span class="nav-number">1.2.</span> <span class="nav-text">计算机组成原理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F"><span class="nav-number">1.3.</span> <span class="nav-text">操作系统</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C"><span class="nav-number">1.4.</span> <span class="nav-text">计算机网络</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#TCP%E5%92%8CUDP%E5%8C%BA%E5%88%AB"><span class="nav-number">1.4.1.</span> <span class="nav-text">TCP和UDP区别</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#TCP%E4%B8%89%E6%AC%A1%E6%8F%A1%E6%89%8B%E5%92%8C%E5%9B%9B%E6%AC%A1%E6%8C%A5%E6%89%8B%E8%BF%87%E7%A8%8B%E5%8F%8A%E5%8E%9F%E5%9B%A0"><span class="nav-number">1.4.2.</span> <span class="nav-text">TCP三次握手和四次挥手过程及原因</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%B8%89%E6%AC%A1%E6%8F%A1%E6%89%8B%E8%BF%87%E7%A8%8B"><span class="nav-number">1.4.2.1.</span> <span class="nav-text">三次握手过程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%B8%89%E6%AC%A1%E6%8F%A1%E6%89%8B%E7%9A%84%E5%8E%9F%E5%9B%A0"><span class="nav-number">1.4.2.2.</span> <span class="nav-text">三次握手的原因</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%9B%9B%E6%AC%A1%E6%8C%A5%E6%89%8B%E8%BF%87%E7%A8%8B"><span class="nav-number">1.4.2.3.</span> <span class="nav-text">四次挥手过程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%AE%BE%E7%BD%AETIME-WAIT%E5%8E%9F%E5%9B%A0"><span class="nav-number">1.4.2.4.</span> <span class="nav-text">设置TIME-WAIT原因</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%9B%9B%E6%AC%A1%E6%8C%A5%E6%89%8B%E5%8E%9F%E5%9B%A0"><span class="nav-number">1.4.2.5.</span> <span class="nav-text">四次挥手原因</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#TCP%E6%8B%A5%E5%A1%9E%E6%8E%A7%E5%88%B6"><span class="nav-number">1.4.3.</span> <span class="nav-text">TCP拥塞控制</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BB%8E%E6%B5%8F%E8%A7%88%E5%99%A8%E8%BE%93%E5%85%A5%E4%B8%80%E4%B8%AAURL%E5%88%B0%E8%BF%94%E5%9B%9E%E5%93%8D%E5%BA%94%E7%9A%84%E5%AE%8C%E6%95%B4%E8%BF%87%E7%A8%8B"><span class="nav-number">1.4.4.</span> <span class="nav-text">从浏览器输入一个URL到返回响应的完整过程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Https%E5%92%8CHttp"><span class="nav-number">1.4.5.</span> <span class="nav-text">Https和Http</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UDP%E4%BF%9D%E8%AF%81%E5%8F%AF%E9%9D%A0%E6%80%A7%E4%BC%A0%E8%BE%93"><span class="nav-number">1.4.6.</span> <span class="nav-text">UDP保证可靠性传输</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Get%E5%92%8CPost"><span class="nav-number">1.4.7.</span> <span class="nav-text">Get和Post</span></a></li></ol></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">余振鑫</p>
  <div class="site-description" itemprop="description">余振鑫的个人博客</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">9</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">余振鑫</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://muse.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>




  















  

  

</body>
</html>
